//
//  Problem215.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/27.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 215. 数组中的第K个最大元素 中等
 
 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

 示例 1:
     输入: [3,2,1,5,6,4], k = 2
     输出: 5
 示例 2:
     输入: [3,2,3,1,2,4,5,5,6], k = 4
     输出: 4
 提示：
 1 <= k <= nums.length <= 105
 -104 <= nums[i] <= 104
 */
class Problem215: NSObject {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        var list = nums
        return findKth(&list, 0, nums.count-1, k-1)
    }
    
    // [3,2,3,1,2,4,5,5,6]
    func findKth(_ nums: inout [Int], _ l: Int, _ r: Int, _ k: Int) -> Int {
        let (start, end) = quickSelect(&nums, l, r, nums[l])
        if start > k {
            return findKth(&nums, l, start-1, k)
        } else if k <= end {
            return nums[k]
        } else {
            return findKth(&nums, end+1, r, k)
        }
    }
    
    func quickSelect(_ nums:inout [Int], _ l: Int, _ r: Int, _ t: Int) -> (Int, Int) {
        if l == r {
            return (l, r)
        }
        
        var start = l
        var end   = r
        
        var i = l
        while i <= end {
            if nums[i] > t {
                nums.swapAt(start, i)
                start += 1
            } else if nums[i] < t {
                nums.swapAt(end, i)
                end -= 1
            } else {
                i += 1
            }
        }
        
        return (start, end)
    }
}
